home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 12880 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.4 KB
  1. Path: beta.nedernet.nl!usenet
  2. From: jos@and.nl (Jos A. Horsmeier)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: fast find algorithm
  5. Date: 3 Apr 1996 10:33:00 GMT
  6. Organization: AND Operations Research B.V.
  7. Message-ID: <4jtk4t$g6r@beta.nedernet.nl>
  8. References: <Dp8wE6.8DG@cix.compulink.co.uk>
  9. NNTP-Posting-Host: klepzeiker.and.nl
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=ISO-8859-1
  12. X-Newsreader: WinVN 0.99.5
  13.  
  14. In article <Dp8wE6.8DG@cix.compulink.co.uk>, setheridge@cix.compulink.co.uk 
  15. wrote:
  16.  
  17. |Does anyone have an search algoritm faster than a binary chop for the 
  18. |following:
  19. |
  20. |find a date from a sorted array of 1500 possible storage locations
  21.  
  22. It depends on the distribution of those 1500 keys, but if those keys
  23. are (more or less) uniformly distributed _and_ those keys have type
  24. double, you could give this a try:
  25.  
  26. let n be the size of the array 'key' and let k be the key we're looking for.
  27. Apply a modified binary chop as follows:
  28.  
  29. int    l, m, h;
  30.  
  31. for (l= 0, h= n-1; l <= h; ) {
  32.  
  33.     m = (h-l)*(k-key[l])/(key[h]-key[l])+l;
  34.     
  35.     if (array[m] == k)
  36.         /* found */
  37.     else if (array[m] < k)
  38.         l= m+1;
  39.     else
  40.         h= m-1;
  41. }
  42.  
  43. On average, this algorithm is (theoretically) faster than a simple
  44. binary chop, where location m is defined as: 'm= (h+l)/2'. But, again,
  45. it all depends on the distribution of the key values ...
  46.  
  47. kind regards,
  48.  
  49. Jos aka jos@and.nl
  50. -- 
  51. Atnwgqkrl gy zit vgksr, ug qshiqwtzoeqs!
  52.  
  53.